#include <stack>
#include <iostream>
#include <stdio.h>
#define N 9
using namespace std;
typedef struct {
    int ord;
    int r;
    int c;
    int dir;
}node;
void showMaze(int maze[N][N]) {
    static int a = 1;
    cout << a++ << endl;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            printf("%3d", maze[i][j]);
        }
        cout << endl;
    }
    cout << endl;
}
bool mazePath(int maze[N][N], int src_r, int src_c, int end_r, int end_c) {
    node* cur;
    int cur_r = src_r;
    int cur_c = src_c;
    int curstep = 1;
    stack<node*> s;
    do {
        if (!maze[cur_r][cur_c]) {
            maze[cur_r][cur_c] = curstep;
            showMaze(maze);
            if (cur_r == end_r && cur_c == end_c)
                return true;
            // new a node into s
            cur = (node*)malloc(sizeof(node)); // 通路才能入栈
            cur->r = cur_r;
            cur->c = cur_c;
            cur->dir = 0;
            cur->ord = curstep;

            s.emplace(cur);

            ++curstep;
            ++cur_c;
        } else {
            // 出栈为了检查栈顶元素是否还有未遍历方向
            cur = s.top();
            s.pop();
            while (cur->dir == 4 && !s.empty()) { // 此时栈顶元素的四周全部遍历完，全不通
                maze[cur->r][cur->c] = -2;
                showMaze(maze);
                free(cur); // 对确定为死路的块进行释放
                cur = s.top();
                s.pop();
                --curstep;
            }
            if (cur->dir < 4) { // 此时的cur还有未遍历方向，需要再次入栈
                ++cur->dir;
                s.emplace(cur); 
                cur_r = cur->r;
                cur_c = cur->c;
                switch(cur->dir) {
                    case 1: ++cur_r; break;
                    case 2: --cur_c; break;
                    case 3: --cur_r; break;
                }                
            }
        }
    } while (!s.empty());

    return false;
}

int main(void) {
    // 0为路，2为墙
    int maze[N][N] = {
        {-1, -1, -1, -1, -1, -1, -1, -1, -1},
        {-1,  0, -1,  0, -1, -1,  0, -1, -1},
        {-1,  0,  0,  0, -1, -1,  0, -1, -1},
        {-1,  0, -1,  0,  0, -1,  0, -1, -1},
        {-1,  0, -1, -1,  0,  0,  0, -1, -1},
        {-1,  0, -1, -1,  0, -1,  0, -1, -1},
        {-1,  0,  0, -1,  0,  0,  0, -1, -1},
        {-1, -1,  0,  0, -1, -1, -1,  0, -1},
        {-1, -1, -1, -1, -1, -1, -1, -1, -1}
    };

    bool ans = mazePath(maze, 1, 1, 7, 3);

    cout << ans << endl;

    return 0;
}
